//
//  ReverseList.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/17.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 24. 反转链表

import UIKit

/*
 剑指 Offer 24. 反转链表

 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。


 示例:

 输入: 1->2->3->4->5->NULL
 输出: 5->4->3->2->1->NULL
  

 限制：

 0 <= 节点个数 <= 5000

  

 注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

 通过次数54,865提交次数72,902
 */

class ReverseList: NSObject {
    
    //双指针法
    func reverseList(_ head: ListNode?) -> ListNode? {

        guard head != nil else{
            return nil
        }
        
        var point1:ListNode? = nil
        var point2 = head
        
        while point2 != nil {
            let tmpNode = point2?.next
            point2?.next = point1
            point1 = point2
            point2 = tmpNode
        }
        return point1
    }
    
    //递归法
    /*
     使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
     此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
     同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
     当递归函数全部出栈后，链表反转完成。

     */
    func reverseList2(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        let node = self.reverseList2(head?.next)
        head?.next?.next = head
        head?.next = nil
        return node
    }
    
}
